/*
剑指 Offer 13. 机器人的运动范围
解题思路：dfs
 */
public class Offer13 {

  public static void main(String[] args) {
    System.out.println(new Offer13().movingCount(3,2,1));
    System.out.println(getSum(388));
    
  }

  public int movingCount(int m, int n, int k) {
    boolean[][] visited = new boolean[m][n];
    return dfs(0, 0, m, n, k, visited);
  }

  private int dfs(int i, int j, int m, int n, int k, boolean[][] visited) {
    if(i >= m || j >= n || k < getSum(i) + getSum(j) || visited[i][j]) {
      return 0;
    }
    visited[i][j] = true;
    return 1 + dfs(i + 1, j, m, n, k, visited) + dfs(i, j + 1, m, n, k, visited);
  }

  private static int getSum(int num){
    int res = num % 10;
    int temp = num / 10;
    while(temp > 0){
      res = res + temp % 10;
      temp = temp / 10;
    }
    return res;
  }
}
